﻿
Imports osi.root.connector

Partial Public Class bt(Of T)
    Protected Friend Class box
        Public ReadOnly v As T

        Public Sub New(ByVal v As T)
            Me.v = v
        End Sub

        Public Shared Function create_node(ByVal v As T) As node
            Return New node(New box(v))
        End Function
    End Class

    Protected Friend Class weighted_box
        Inherits box

        Public left_weight As UInt32
        Public right_weight As UInt32

        Public Sub New(ByVal v As T)
            MyBase.New(v)
        End Sub

        Public Shared Shadows Function create_node(ByVal v As T) As node
            Return New node(New weighted_box(v))
        End Function
    End Class

    Protected Friend Class heighted_box
        Inherits box

        Public left_height As UInt32
        Public right_height As UInt32

        Public Sub New(ByVal v As T)
            MyBase.New(v)
        End Sub

        Public Shared Shadows Function create_node(ByVal v As T) As node
            Return New node(New heighted_box(v))
        End Function

        'make sure all the height recorded in heighted_box are correct
        Public Shared Sub assert_height(ByVal r As node)
            k_assert(Not r Is Nothing)
            k_assert(r.left_subtree_height() = r.heighted_box().left_height)
            k_assert(r.right_subtree_height() = r.heighted_box().right_height)
            If r.has_left_child() Then
                assert_height(r.left_child())
            End If
            If r.has_right_child() Then
                assert_height(r.right_child())
            End If
        End Sub

        Public Shared Sub debug_assert_height(ByVal r As node)
#If DEBUG Then
            assert_height(r)
#End If
        End Sub
    End Class
End Class
